package leetcodev1.字符串;

import leetcodev1.链表.Solution;

import java.util.ArrayList;
import java.util.List;

public class LeetCode93 {
    public static void main(String[] args) {
        LeetCode93 leetCode93 = new LeetCode93();
        List<String> strings = leetCode93.restoreIpAddresses("25525511135");
    }

    //题目切分成四段
    //条件[0,255]间
    //1.回溯 肯定有结果
    //2.dp ij是否有效
    //3.回溯+dp
    List<String> ret = new ArrayList<>();

    //效率低
    public List<String> restoreIpAddresses(String s) {
        int length = s.length();
        boolean[][] dict = new boolean[length + 1][length + 1];
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j <= length; j++) {
                dict[i][j] = isValidateIp(s.substring(i, j));
            }
        }
        dfs(0, 0, "", dict, length, s);

        return ret;
    }

    private void dfs(int start, int level, String route, boolean[][] dict, int length, String s) {
        if (level > 4) {
            return;
        }

        if (level == 4 && start == length) {
            ret.add(route.substring(0, route.length() - 1));// Create a copy, don't share the array
            return;
        }

        for (int i = 0; i < 3; i++) {
            if (!dict[start][start + 1 + i]) {
                continue;
            }

            dfs(start + 1 + i, level + 1, route + s.substring(start, i) + ".", dict, length, s);
        }
    }

    private boolean isValidateIp(String ip) {
        long ipNum = Long.parseLong(ip);
        if (ipNum < 0 || ipNum > 255) {
            return false;
        }

        return ip.length() <= 1 || ip.charAt(0) != '0';
    }
}


class Answer93 {
    static final int SEG_COUNT = 4;//常量
    List<String> ans = new ArrayList<String>();//结果
    int[] segments = new int[SEG_COUNT];//临时结果 不需要回溯，每次都会重新覆盖

    public List<String> restoreIpAddresses(String s) {
        segments = new int[SEG_COUNT];
        dfs(s, 0, 0);
        return ans;
    }

    public void dfs(String s, int segId, int segStart) {
        // 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
        if (segId == SEG_COUNT) {
            if (segStart == s.length()) {
                StringBuffer ipAddr = new StringBuffer();
                for (int i = 0; i < SEG_COUNT; ++i) {
                    ipAddr.append(segments[i]);
                    if (i != SEG_COUNT - 1) {
                        ipAddr.append('.');
                    }
                }
                ans.add(ipAddr.toString());//添加结果
            }
            return;
        }

        // 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
        if (segStart == s.length()) {
            return;
        }

        // 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
        if (s.charAt(segStart) == '0') {
            segments[segId] = 0;
            dfs(s, segId + 1, segStart + 1);
        }

        // 一般情况，枚举每一种可能性并递归
        int addr = 0;
        for (int segEnd = segStart; segEnd < s.length(); ++segEnd) {
            addr = addr * 10 + (s.charAt(segEnd) - '0');
            //255
            if (addr > 0 && addr <= 0xFF) {
                segments[segId] = addr;
                dfs(s, segId + 1, segEnd + 1);
            } else {
                break;
            }
        }
    }
}
